from collections import deque


class TreeNode:
    def __init__(self, x=0):
        self.val = x
        self.left = None
        self.right = None


def max_weight_in_tree(root: TreeNode):
    """
    求一颗二叉树的最大宽度
    :param root:
    :return:
    """
    if not root:
        return
    queue = deque()
    queue.append(root)
    res = 0
    while queue:
        res = max(res, len(queue))
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return res


if __name__ == "__main__":
    head = TreeNode(6)
    head.left = TreeNode(3)
    head.left.left = TreeNode(1)
    head.left.left.right = TreeNode(2)
    head.left.right = TreeNode(4)
    head.left.right.right = TreeNode(5)
    head.right = TreeNode(9)
    head.right.left = TreeNode(8)
    head.right.left.left = TreeNode(7)
    head.right.right = TreeNode(10)

    print(max_weight_in_tree(head))